package com.hdu.point_offer;

public class lcr131 {
    class Solution {
        public int cuttingBamboo(int n) {
            int tail = (n % 3 == 0 ? 1 : (n % 3 == 1 ? 4 : 2));
            int pow = (tail == 1 ? n : (n - tail)) / 3;
            return (int) pow(3L, pow) * tail;
        }

        long pow(long x, int n) {
            long ans = 1;
            while (n > 0) {
                if ((n & 1) == 1) {
                    ans = ans * x;
                }
                x = x * x;
                n >>= 1;
            }
            return ans;
        }
    }
}
